1. Field of the Invention
The present invention relates to a technique for precisely drawing graphs of implicit functions for use with science and engineering calculations, in particular to a graphic drawing apparatus and method for precisely and automatically drawing graphics represented as a set of zeros of a polynomial with designated accuracy.
2. Description of the Related Art
In the recent science and engineering fields, the results of science and engineering calculations have been displayed by using computers so as to understand the phenomena, discern the background, and discover new problems. In displaying calculated results, it is a most fundamental problem to display a set of x and y values represented by an expression of relation f(x, y)=0, which has two variables and defines a kind of an implicit function y in x as a graph on an xy coordinate plane. However, unless the function f(x, y) is very simple, it is very difficult to precisely and accurately draw a graph of f(x, y)=0.
When the function f(x, y) is given as a bivariate polynomial, a multiple-valued function y=Y(x) in which f(x, y)=0 is solved with respect to the variable y is referred to as an algebraic function. The classes of this function include not only simple graphics such as straight lines, parabolas, circles, ovals, ellipses, and hyperbolas, but complicated curves whose shapes cannot be imagined with the form of the function. In such complicated curves, part of curves may be degenerated to points. In the current graphic techniques using computers, graphics represented by algebraic functions are sometimes drawn. Thus, techniques for precisely and automatically drawing graphics represented by algebraic functions are important tasks to be solved.
As conventional methods for drawing graphics represented by algebraic functions using computers, an all region pixel sign determining method and tracking methods have been proposed. The tracking methods are further categorized as curve tracking method (using differential equations), adjacent pixel tracking method, curve interpolating method, and contour line drawing method. In each method, an apparatus display region on the screen of a display device connected to the computer is made correspondent with a logical region of an xy coordinate plane by a predetermined mapping.
In the all region pixel sign determining method (Mitara, A. K., Graphing Implicit Functions f(x, y)=0, Applied Mathematics and Computation, 39, pp. 199-205, 1990), when a curve represented by an implicit function f(x, y)=0 is drawn on a screen (composed of a set of pixels arranged in a matrix shape) of a display device, a criterion for determining that a point on the curve is present in a particular pixel. According to this method, pixels in a display region are mapped onto the xy coordinate plane. Corresponding to signs (positive, negative, or zero) of values of the function f(x, y) at several representative points on the boundary lines of each pixel and its adjacent pixels, zeros of the function f(x, y) in each pixel point are determined based on the intermediate value theorem with respect to a continuous function.
FIG. 1 shows an example of representative points on boundary lines between adjacent pixels on the xy coordinate plane. As shown in FIG. 1, points (x.sub.1, y.sub.1), (x.sub.1, y.sub.2), (x.sub.2, y.sub.1), and (x.sub.2, y.sub.2) at four corners of a pixel 1 are designated representative points. The function values f(x.sub.1, y.sub.1), f(x.sub.1, y.sub.2), f(x.sub.2, y.sub.1), and f(x.sub.2, y.sub.2) are calculated and then the signs thereof are determined. For example, if the sign of f(x.sub.1, y.sub.1) is different from the sign of f(x.sub.2, y.sub.1) (other than zero), it is clear that a zero is present between the two points (x.sub.1, y.sub.1) and (x.sub.2, y.sub.1) according to the intermediate value theorem. In addition, if the sign of f(x.sub.1, y.sub.1) is different from the sign of f(x.sub.1, y.sub.2), a zero is present between two points (x.sub.1, y.sub.1) and (x.sub.1, y.sub.2).
If there are positive values and negative values as the four function values at the four representative points, there is a zero of the function f(x, y) in the pixel 1. In other words, it is determined that a point on the curve f(x, y)=0 is present and the pixel 1 is plotted. On the other hand, if one of the four function values is zero, since a corresponding representative point is present on the curve f(x, y)=0, a proper one of four pixels surrounding the representative value is plotted. If all the four function values are positive or negative, it is assumed that no zero is present in the pixel 1, and the pixel 1 is not plotted. When such a determining process is performed for all pixels that compose the display region, the curve f(x, y)=0 can be automatically drawn as a set of pixels containing zeros of the function f(x, y).
Since the all region pixel sign determining method does not require the evaluation of a differential of the function f(x, y), complicated differentiating calculation is omitted. In addition, this method is applicable for functions that cannot be differentiated. In this method, when the number of pixels in the display region is increased, the image quality is improved. However, since the signs of all pixels of the region should be determined, the amount of calculation increases, thereby decreasing the process speed. However, when such a calculation is performed by a high speed parallel computer, the calculation speed can be remarkably improved. Moreover, an application of the all region pixel sign determining method for non-linear equations has been proposed.
On the other hand, when the tracking methods (that will be described later) are used, since adjacent pixels to be plotted are determined starting from a point on the curve f(x, y)=0, unlike with the all region pixel sign determining method, it is not necessary to calculate pixels in the all display region for determining the signs thereof.
In the adjacent pixel tracking method, when one zero point of the function f(x, y) is given, adjacent pixels containing zeros connected to the given point are successively determined. Thus, a curve successively connected to the given zero is tracked and displayed.
When adjacent pixels to be connected are determined, as with the all region pixel sign determining method, a determining method corresponding to the intermediate value theorem can be used. For example, signs of values of the function f(x, y) at several representative points starting from a given point on a given curve f(x, y)=0 are determined and pixels to be connected are determined. Thus, one branch of the curve is tracked (as disclosed in Japanese Patent Laid-Open Publication No. 2-304684).
To determine the direction of a pixel to be connected, a technique in which the function f(x, y) in the vicinity of a particular point on the curve f(x, y)=0 is differentiated in various manners is known.
In the curve tracking method using differential equations (Nakatsuyama, M. et el., Curve Generation of Implicit Functions by Incremental Computers, Comput. & Graphics, 7, pp. 161-167, 1983), variables x and y are treated as functions x(t) and y(t) with respect to a parameter t. When one zero of the function f(x, y) is given, the curve f(x, y)=0 is drawn. By numerically solving a differential equation with respect to the parameter t, points on the curve f(x, y)=0 are successively obtained. Pixels corresponding to the obtained points are plotted on the display region on the screen.
According to this method, when a function form of f(x, y) is given, a differential equation that represents the curve f(x, y)=0 is not uniquely obtained. As an example, the following simultaneous equations are often used. EQU d.sub.x /d.sub.t =f.sub.y (x, y) EQU d.sub.y /d.sub.t =-f.sub.x (x, y) (1) EQU f.sub.x (x, y)=.differential.f(x, y)/.differential.x EQU f.sub.y (x, y)=.differential.f(x, y)/.differential.y
When the given zero is at (x.sub.0, y.sub.0), the expression (1) can be numerically solved with initial conditions x(0)=x.sub.0 and y(0)=y.sub.0 at t=0. When the numeric solutions of the expression (1) are plotted corresponding to the pixels of the display region, a graph of the curve f(x, y)=0 can be obtained.
In the curve interpolating method, the coordinate values of plural points on the curve f(x, y)=0 are numerically calculated. These points are properly interpolated so as to display the results as a graph. In this method, since a point on a curve represented by f(x, y)=0 is obtained, the variable y is fixed to a particular value y.sub.k. Plural values of the variable x that satisfy f(x, y.sub.k)=0 are numerically obtained. Sets of obtained values of x and y.sub.k are treated as coordinates of points on the corresponding curve. The value of y.sub.k in the display region can be varied with a predetermined pitch. Points on the curve corresponding to the fixed value are obtained as coordinate values of plural points that satisfy f(x, y)=0. When the obtained points are interpolated with a polygonal line or an appropriate smooth curve, an integral curve of f(x, y)=0 can be obtained.
In the method using the contour line drawing method, coordinate values at plural points on a three-dimensional curved surface z=f(x, y) in an xyz coordinate space are obtained. The obtained values of these points are interpolated on a appropriate curved surface in the proper three-dimensional space and an intersection line with an xy plane (z=0) is obtained. In this method, the display region mapped on the xy plane is divided in a lattice shape. The value of the function f(x, y) at each lattice point (x.sub.m, y.sub.m) is calculated with z coordinate value z.sub.mn =f(x.sub.m, y.sub.n). A set of points {(x.sub.m, y.sub.n, z.sub.mn)} in the three-dimensional space represent points on the curved surface z=f(x, y). An appropriate curved surface that interpolates such points is determined and values of xy coordinates at points on the intersection line of the curved surface and the xy plane are calculated. Thus, a curve that approximates the curve f(x, y)=0 on the xy plane is obtained.
When an intersection line of a plane z=c.sub.k, instead of z=0, that is in parallel with the xy plane, and the interpolated curved surface is obtained, constant c.sub.k being varied with a predetermined pitch, contour lines of the curved surface z=f(x, y) can be obtained.
In the method using the contour line drawing method, it is not necessary to numerically solve an equation f(x, y.sub.k)=0 unlike with the curve interpolating method. Instead, when a coordinate value (x.sub.m, y.sub.n) at a lattice point is substituted into the function f(x, y), the value of z.sub.mn can be obtained.
However, in the above-described drawing methods, there are following problems.
In the conventional drawing methods, the most practical method is the all region pixel sign determining method. According to this method, graphs of most algebraic functions can be stably drawn. In the all region pixel sign determining method, the presence of a zero of the function f(x, y) in each pixel is determined based on the intermediate value theorem. According to theorem, although the presence of a zero of a continuous function in a designated interval can be proved, the absence thereof cannot be proved.
For example, in FIG. 1, even if the sign of the function value f(x.sub.1, y.sub.1) is the same as the sign of the function value f(x.sub.2, y.sub.1), the absence of a zero of the function f(x, y) between the two points (x.sub.1, y.sub.1) and (x.sub.2, y.sub.1) cannot be proved. Thus, even if the signs of the values of f(x, y) at four boundary representative points at the pixel 1 are the same, a zero of the function f(x, y) may be theoretically present in the pixel 1. This situation occurs when plural curves that are represented by f(x, y)=0 are very close to each other, there are plural branches of curves in a pixel, and a singular point or a similar situation takes place. In this case, even if there is a real zero of the function f(x, y), a corresponding pixel is not plotted.
FIG. 2 shows an example of a sign distribution of the function f(x, y) in the vicinity of a singular point on the xy plane in the case that the curve f(x, y)=0 has the singular point. In FIG. 2, two curves that are represented by f(x, y)=0 have a point of contact SP in a pixel 2-3. This contact point SP is a singular point. The two curves share a tangent line at the singular point SP. The display region is divided into four regions (upper, lower, left, and right regions) by the curve f(x, y)=0 about the singular point SP. The values of the function f(x, y) in the upper and lower regions are positive. The values of the function f(x, y) in the left and right regions are negative. Thus, at all four boundary representative points P1, P2, P3, and P4 of the pixel 2-3, the values of the function f(x, y) are positive. In the above-described all region pixel sign determining method, when all function values at boundary representative values are the same, the corresponding pixel is not plotted. Thus, the pixel 2-3 in FIG. 2 is not displayed on the screen. Due to the same reason, the pixels 2-1, 2-2, 2-4, and 2-5 that are arranged on the left and right of the pixel 2-3 are not displayed on the screen.
Thus, in the all region pixel sign determining method, the pixels 2-1 to 2-5 in the vicinity of the singular point SP of the curve f(x, y)=0 cannot be plotted. Thus, an abnormal blank region appears on the display screen. Such a blank region may take place at a portion other than the vicinity of the singular point. In this case, when the enlargement ratio is increased, the curve can be obtained. However, in the vicinity of the singular point, even if the enlargement ratio is increased, the curve cannot be correctly obtained.
FIG. 3 is an enlarged view showing the vicinity of a singular point in the case that a display region is appropriately mapped to a logical region on the xy plane and enlarged and the square region 3 shown in FIG. 2 is treated as a new unit pixel. In FIG. 3, the values of the function f(x, y) at boundary representative points P5, P6, P7, and P8 of the pixel 3 including the singular point SP are positive. Thus, the pixel 3 is not displayed on the screen. Even if the calculating accuracy is raised in such a manner that the values of a polynomial f(x, y) are precisely calculated by a rational number calculation, the pixel 3 is not displayed. Thus, a correct graph cannot be obtained.
In addition, in the adjacent pixel tracking method and the curve tracking method using differential equation, there are problems of how a zero of the function f(x, y) that is the start point of the tracking is designated and how several curves that are not connected each other are obtained. Thus, it is clear that such methods are imperfect.
In the adjacent pixel tracking method, when adjacent pixels to be connected are determined according to the intermediate value theorem, the same problems as the all region pixel sign determining method take place.
When a curve f(x, y)=0 is tracked with a differential equation, since the differential value of the function f(x, y) at a singular point becomes 0, even if the value of the parameter t increases, the coordinate value (x(t), y(t)) is not updated. Thus, the curve can be no more extended. Thus, the solution in the vicinity of the singular point cannot be obtained. Consequently, branches that pass through the singular point should be treated as independent curves that are not connected. For example, in the example shown in FIG. 2, since the differential of f.sub.x (x, y) at the singular point SP is zero, the vicinity of this point cannot be precisely drawn.
In the curve interpolating method, when there are points on a plurality of curves corresponding to adjacent fixed values y.sub.k and y.sub.k+1, the connections are not uniquely determined. In particular, in the vicinity of a singular point, if plural points are very close to each other, it is very difficult to determine the correct connecting relation.
In the method using the contour line drawing method, the interpolating process in the three-dimensional space is very complicated. In this method, although a long calculating time is required, a corresponding correct connecting relation of curves cannot be expected. In particular, when a curve to be obtained includes a singular point, it is impossible to obtain the curve.
The above-described tracking methods involve various problems when drawing algebraic functions. As a critical cause of which such tracking methods cannot be used, when plural curves are represented by f(x, y)=0, it is difficult to completely obtain all tracking start points on the curves. To track all curves and determine that they have been drawn, it should be determined whether or not each pixel contains points on the curves for all pixels in the display region. Thus, the all region pixel sign determining method is called in the above-described tracking methods.
Consequently, even if any conventional drawing method is used, a region in which curves are very close to each other and a singular point or similar situation takes place cannot be correctly drawn.